#ifndef __BINARYTREE_H_
#define __BINARYTREE_H_

#include<iostream>
#include<LinkQueue.h>


class BinaryTree
{
    using ElementType = int;
public:
    BinaryTree();
    
    void Insert(const ElementType& element);

    void show();

    void Remove(const ElementType& element);

ElementType* FindByElement(const ElementType&element);





private:
   struct Node
   {

    Node(const ElementType &data):data(data)
    {
        left = right = nullptr;
    }

    ElementType data;
    Node * left;
    Node * right;
   };
   
    Node *root;  //找到根节点 找到所有节点

    Node* InsertNode(Node*node,const ElementType&element);

    Node* RemoveNode(Node*node,const ElementType&element);

    Node* GetMinNode(Node*node);

    ElementType* FindNode(Node*node,const ElementType&element);

    void HeightTravel();

    void PrevTraval(Node *node)
    {
        if(node == nullptr)
            return;
        std::cout<<node->data<<" ";
        PrevTraval(node->left);
        PrevTraval(node->right);
        
    }

    void MidTraval(Node*node)
    {
        if(node == nullptr)
            return;
        MidTraval(node->left);
        std::cout<<node->data<<" ";
        MidTraval(node->right);   
    }

    void PostTraval(Node*node)
    {
        if(node == nullptr)
            return;
        PostTraval(node->left);
        PostTraval(node->right);
        std::cout<<node->data<<" ";
    }

    // 右旋
    Node*RotateRight(Node*node);

    // 左旋
    Node*RotateLeft(Node*node);

    //左右旋
    Node*RotateLeftRight(Node*node);

    //右左旋
    Node*RotateRightLeft(Node*node);

    int GetNodeHeight(Node* node);
    int LRDevition(Node*node);


};






#endif